home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 #2 / Ham Radio 2000 - Volume 2.iso / HAMV2 / TCP_IP / TNOS230S / LZW.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-12-23  |  15.4 KB  |  585 lines
  1. /*        SM0RGV data compression routines.
  2.  * This file implements the Lempel-Ziv Welch (LZW) data compression
  3.  * algorithm but with a variable code size, as in GIF format files.
  4.  *
  5.  * Copyright 1990 by Anders Klemets, SM0RGV. Permission granted for
  6.  * non-commercial distribution only.
  7.  */
  8.  
  9. #include "global.h"
  10. #include "commands.h"
  11. #include "ctype.h"
  12. #ifdef    LZW
  13. #include "mbuf.h"
  14. #include "proc.h"
  15. #include "lzw.h"
  16. #include "session.h"
  17.  
  18.  
  19. #if !defined(_lint)
  20. static char rcsid[] OPTIONAL = "$Id: lzw.c,v 1.13 1996/12/23 22:44:37 root Exp root $";
  21. #endif
  22.  
  23. static void fastencode (struct usock * up, char data);
  24. static void morebits (struct lzw * lzw);
  25. static void cleartbl (struct lzw * lzw);
  26. static void addtobuffer (struct usock * up, int32 code);
  27. static void addchar (char data, struct lzw * lzw);
  28. static void getstring (int32 code, struct lzw * lzw);
  29. static char firstchar (int32 code, struct lzw * lzw);
  30. static void decodetbl (int32 code, struct lzw * lzw);
  31. static int32 nextcode (struct usock * up);
  32.  
  33.  
  34.  
  35. int
  36. dolzw (int argc, char **argv, void *p OPTIONAL)
  37. {
  38.     if (argc > 1) {
  39.         switch (tolower (*argv[1])) {
  40.             case 'm':
  41.                 if (argc == 2)
  42.                     tprintf ("LZW mode: %s\n", Lzwmode ? "fast" : "compact");
  43.                 else
  44.                     Lzwmode = (tolower (*argv[2]) == 'f');
  45.                 return 0;
  46.             case 'b':
  47.                 argc--;
  48.                 argv++;
  49.                 return setintrc (&Lzwbits, "LZW bits", argc, argv, 9, 16);
  50.             case '=':
  51.                 if (argc == 3) {
  52.                     struct session *sp;
  53.  
  54.                     if ((sp = sessptr (argv[2])) != NULLSESSION) {
  55.                         lzwinit (sp->s, Lzwbits, Lzwmode);
  56.                     }
  57.                 }
  58.                 return 0;
  59.             default:
  60.                 break;
  61.         }
  62.     }
  63.     tputs ("Usage: lzw <mode|bits>\n");
  64.     return -1;
  65. }
  66.  
  67.  
  68.  
  69. /* Initialize a socket for compression. Bits specifies the maximum number
  70.  * of bits per codeword. The input and output code tables might grow to
  71.  * about (2^bits * 3) bytes each. The bits parameter does only serve as a
  72.  * recommendation for the decoding, the actual number of bits may be
  73.  * larger, but not never more than 16.
  74.  */
  75. void
  76. lzwinit (s, bits, mode)
  77. int s;                /* socket to operate on */
  78. int bits;            /* maximum number of bits per codeword */
  79. int mode;            /* compression mode, LZWCOMPACT or LZWFAST */
  80. {
  81. struct usock *up;
  82.  
  83.     if ((up = itop (s)) == NULLUSOCK)
  84.         return;
  85.     up->zout = (struct lzw *) callocw (1, sizeof (struct lzw));
  86.     up->zin = (struct lzw *) callocw (1, sizeof (struct lzw));
  87.  
  88.     up->zout->codebits = LZWBITS;
  89.     if (bits < LZWBITS)
  90.         up->zout->maxbits = LZWBITS;
  91.     if (bits > 16 || bits == 0)
  92.         up->zout->maxbits = 16;
  93.     if (bits >= LZWBITS && bits <= 16)
  94.         up->zout->maxbits = bits;
  95.     up->zout->nextbit = 0;
  96.     up->zout->prefix = -1;
  97.     up->zout->version = -1;
  98.     up->zout->code = -1;
  99.     up->zout->mode = (char) mode;
  100.     up->zout->next = ZFLUSH + 1;    /* used only in LZWFAST mode */
  101.     up->zin->codebits = LZWBITS;
  102.     up->zin->maxbits = -1;
  103.     up->zin->nextbit = 0;
  104.     up->zin->prefix = -1;
  105.     up->zin->version = -1;
  106.     up->zin->code = -1;
  107.     up->zin->next = ZFLUSH + 1;
  108.     up->zin->mode = LZWCOMPACT;
  109.     up->zin->buf = NULLBUF;
  110. }
  111.  
  112.  
  113. void
  114. lzwfree (struct usock *up)
  115. {
  116.     if (up->zout != NULLLZW) {
  117.         cleartbl (up->zout);
  118.         free ((char *) up->zout);
  119.         up->zout = NULLLZW;
  120.     }
  121.     if (up->zin != NULLLZW) {
  122.         cleartbl (up->zin);
  123.         free_q (&up->zin->buf);
  124.         free ((char *) up->zin);
  125.         up->zin = NULLLZW;
  126.     }
  127. }
  128.  
  129.  
  130.  
  131. /* LZW encoding routine.
  132.  * See if the string specified by code + data is in the string table. If so,
  133.  * set prefix equal to the code of that string. Otherwise insert code + data
  134.  * in the string and set prefix equal to data.
  135.  */
  136. void
  137. lzwencode (int s, char data)
  138. {
  139. struct usock *up;
  140. register struct lzw *lzw;
  141. int32 code, pagelim;
  142. register unsigned int i, j;
  143.  
  144.     if ((up = itop (s)) == NULLUSOCK)
  145.         return;
  146.     lzw = up->zout;
  147.     code = up->zout->prefix;
  148.     /* the first byte sent will be the version number */
  149.     if (lzw->version == -1) {
  150.         lzw->version = ZVERSION;
  151.         up->obuf->data[up->obuf->cnt++] = uchar(lzw->version);
  152.         /* then send our recommended maximum number of codebits */
  153.         up->obuf->data[up->obuf->cnt++] = uchar(lzw->maxbits);
  154.     }
  155.     lzw->cnt++;
  156.     if (code == -1) {
  157.         lzw->prefix = (int32) uchar (data);
  158.         return;
  159.     }
  160.     if (lzw->mode == LZWFAST) {
  161.         fastencode (up, data);
  162.         return;
  163.     }
  164.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  165.     if (code <= ZFLUSH)
  166.         i = j = 0;
  167.     else {
  168.         i = (int16) ((code - ZFLUSH) / LZWBLK);
  169.         j = (int16) (int) ((code - ZFLUSH) % LZWBLK);
  170.     }
  171.     if (lzw->tu.tbl == (struct zentry **) 0)
  172.         lzw->tu.tbl = (struct zentry **) callocw (1, sizeof (struct zentry *) * (unsigned long) pagelim);
  173.  
  174.     for (;;) {
  175.         if (itop (s) == NULLUSOCK)    /* the connection has been closed */
  176.             return;
  177.         if (up->zout == NULLLZW)    /* ...or is about to be closed */
  178.             return;
  179.         if (lzw->tu.tbl[i] == (struct zentry *) 0) {
  180.             lzw->tu.tbl[i] = (struct zentry *) mallocw (LZWBLK * sizeof (struct zentry));
  181.             memset ((char *) lzw->tu.tbl[i], 0xff, LZWBLK * sizeof (struct zentry));
  182.         }
  183.         while (j < LZWBLK) {
  184.             if (lzw->tu.tbl[i][j].data == data && lzw->tu.tbl[i][j].code == (int16) code) {
  185.                 lzw->prefix = (int32) (i * LZWBLK + j + ZFLUSH + 1);
  186.                 return;
  187.             }
  188.             if (lzw->tu.tbl[i][j].code == 0xffff) {
  189.                 lzw->tu.tbl[i][j].code = (int16) code;
  190.                 lzw->tu.tbl[i][j].data = data;
  191.                 addtobuffer (up, code);
  192.                 lzw->prefix = (int32) uchar (data);
  193.                 lzw->next++;
  194.                 if (lzw->next == (int32) 1 << lzw->codebits)
  195.                     /* the current table is now full */
  196.                     morebits (lzw);
  197.                 if (lzw->next + 1 == (int32) 1 << lzw->maxbits) {
  198.                     /* The last codeword has been reached.
  199.                      * (Or last - 1.) Signal this and start all
  200.                      * over again.
  201.                      */
  202.                     addtobuffer (up, lzw->prefix);
  203.                     if (lzw->next + 1 == (int32) 1 << lzw->codebits)
  204.                         morebits (lzw);
  205.                     addtobuffer (up, ZCC);
  206.                     cleartbl (lzw);
  207.                 }
  208.                 return;
  209.             }
  210.             ++j;
  211.         }
  212.         kwait (NULL);
  213.         ++i;
  214.         j = 0;
  215.     }
  216. }
  217.  
  218.  
  219.  
  220. /* Used when LZWFAST mode is selected. Memory usage approx. (2^bits * 5)
  221.  * bytes.
  222.  */
  223. static void
  224. fastencode (struct usock *up, char data)
  225. {
  226. register struct zfast *z;
  227. register struct mbuf *bp;
  228. register struct lzw *lzw = up->zout;
  229. int32 code = up->zout->prefix;
  230. register int16 cnt, h;
  231.  
  232.     if (lzw->tu.bpp == NULLBUFP)
  233.         lzw->tu.bpp = (struct mbuf **) callocw (1, sizeof (struct mbuf *) * ZHASH);
  234.  
  235.     h = lobyte (code);
  236.     h ^= hibyte (code);        /*lint !e704 */
  237.     h ^= data;
  238.     h = h % ZHASH;
  239.     if (lzw->tu.bpp[h] == NULLBUF)
  240.         lzw->tu.bpp[h] = ambufw (LZWBLK);
  241.     bp = lzw->tu.bpp[h];
  242.     cnt = bp->cnt / sizeof (struct zfast);
  243.  
  244.     z = (struct zfast *) bp->data;
  245.     while (cnt > 0) {
  246.         if (z->data == data && z->code == (int16) code) {
  247.             lzw->prefix = (int32) z->owncode;
  248.             return;
  249.         }
  250.         z++;
  251.         if (--cnt == 0) {
  252.             if (bp->next == NULLBUF)
  253.                 break;
  254.             bp = bp->next;
  255.             cnt = bp->cnt / sizeof (struct zfast);
  256.  
  257.             z = (struct zfast *) bp->data;
  258.         }
  259.     }
  260.     if (bp->size - bp->cnt >= (int) sizeof (struct zfast)) {
  261.         z = (struct zfast *) &bp->data[bp->cnt];
  262.         bp->cnt += sizeof (struct zfast);
  263.     } else {
  264.         bp->next = ambufw (LZWBLK);
  265.         z = (struct zfast *) bp->next->data;
  266.         bp->next->cnt = sizeof (struct zfast);
  267.     }
  268.     z->code = (int16) code;
  269.     z->data = data;
  270.     z->owncode = (int16) lzw->next++;
  271.     addtobuffer (up, code);
  272.     lzw->prefix = (int32) uchar (data);
  273.     if (lzw->next == (int32) 1 << lzw->codebits)
  274.         /* Increase the number of bits per codeword */
  275.         morebits (lzw);
  276.  
  277.     if (lzw->next + 1 == (int32) 1 << lzw->maxbits) {
  278.         /* The last codeword has been reached. (Or last - 1.)
  279.          * Signal this and start all over again.
  280.          */
  281.         addtobuffer (up, lzw->prefix);
  282.         if (lzw->next + 1 == (int32) 1 << lzw->codebits)
  283.             morebits (lzw);
  284.         addtobuffer (up, ZCC);
  285.         cleartbl (lzw);
  286.     }
  287.     kwait (NULL);
  288. }
  289.  
  290.  
  291.  
  292. /* increase the number of significant bits in the codewords, and increase
  293.  * the size of the string table accordingly.
  294.  */
  295. static void
  296. morebits (struct lzw *lzw)
  297. {
  298. struct zentry **newt;
  299. int32 pagelim, oldp;
  300.  
  301.     oldp = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  302.     lzw->codebits++;
  303.     if (lzw->mode == LZWFAST)
  304.         return;
  305.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  306.     newt = (struct zentry **) callocw (1, sizeof (struct zentry *) * (unsigned long) pagelim);
  307.     memcpy (newt, lzw->tu.tbl, sizeof (struct zentry *) * (unsigned long) oldp);
  308.  
  309.     free ((char *) lzw->tu.tbl);
  310.     lzw->tu.tbl = newt;
  311. }
  312.  
  313.  
  314.  
  315. static void
  316. cleartbl (struct lzw *lzw)
  317. {
  318. int32 pagelim, i;
  319.  
  320.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  321.     lzw->codebits = LZWBITS;
  322.     lzw->prefix = -1;
  323.     lzw->next = ZFLUSH + 1;
  324.     if (lzw->tu.p == NULL)
  325.         return;
  326.     if (lzw->mode == LZWCOMPACT)
  327.         for (i = 0; i < pagelim; ++i)
  328.             free ((char *) lzw->tu.tbl[i]);
  329.     else
  330.         for (i = 0; i < ZHASH; ++i)
  331.             free_p (lzw->tu.bpp[i]);
  332.     free ((char *) lzw->tu.p);
  333.     lzw->tu.p = NULL;
  334. }
  335.  
  336.  
  337.  
  338. /* Add a codeword to the code stream. Nextbit indicates at which bit in the
  339.  * code stream should be written first. The codeword ZFLUSH is used to
  340.  * pad the buffer to a byte boundary when the buffer will be flushed.
  341.  * The remaining bits of the ZFLUSH codeword are sent in the next buffer.
  342.  */
  343. static void
  344. addtobuffer (struct usock *up, int32 code)
  345. {
  346.     if (up->zout->code != -1) {
  347.         /* Insert remaining bits of ZFLUSH codeword */
  348.         up->obuf->data[up->obuf->cnt] = uchar(up->zout->code >> up->zout->flushbit);    /*lint !e704 */
  349.         if (up->zout->flushbit + 8 >= up->zout->codebits) {    /* done */
  350.             up->zout->nextbit = (up->zout->codebits - up->zout->flushbit) % 8;
  351.             if (up->zout->nextbit == 0)
  352.                 ++up->obuf->cnt;
  353.             up->zout->code = -1;
  354.         } else {
  355.             /* not done yet */
  356.             ++up->obuf->cnt;
  357.             up->zout->flushbit += 8;
  358.             addtobuffer (up, code);
  359.             return;
  360.         }
  361.     }
  362.     /* normal codewords are treated here */
  363.     if (up->zout->nextbit == 0) {
  364.         /* we are at a byte boundary */
  365.         if (code == ZFLUSH) {
  366.             up->zout->flushbit = 0;
  367.             up->zout->code = ZFLUSH;
  368.             return;
  369.         }
  370.         up->obuf->data[up->obuf->cnt++] = uchar(code);
  371.     } else
  372.         up->obuf->data[up->obuf->cnt++] |= uchar(code << up->zout->nextbit);    /*lint !e703 */
  373.     if (code == ZFLUSH) {
  374.         /* interrupt here and save the rest of the ZFLUSH
  375.          * codeword for later.
  376.          */
  377.         up->zout->flushbit = 8 - up->zout->nextbit;
  378.         up->zout->code = ZFLUSH;
  379.         return;
  380.     }
  381.     up->obuf->data[up->obuf->cnt] = uchar(code >> (8 - up->zout->nextbit));    /*lint !e704 */
  382.     /* start on a third byte if necessary */
  383.     if (16 - up->zout->nextbit < up->zout->codebits)
  384.         up->obuf->data[++up->obuf->cnt] = uchar(code >> (16 - up->zout->nextbit));    /*lint !e704 */
  385.     up->zout->nextbit = (up->zout->nextbit + up->zout->codebits) % 8;
  386.     if (up->zout->nextbit == 0)
  387.         ++up->obuf->cnt;
  388. }
  389.  
  390.  
  391.  
  392. void
  393. lzwflush (struct usock *up)
  394. {
  395.     /* interrupt the encoding process and send the prefix codeword */
  396.     if (up->zout->prefix != -1) {
  397.         addtobuffer (up, up->zout->prefix);
  398.         if (up->zout->next + 1 == (int32) 1 << up->zout->codebits)
  399.             morebits (up->zout);
  400.         up->zout->prefix = -1;
  401.     }
  402.     /* signal this by sending the ZFLUSH codeword */
  403.     addtobuffer (up, ZFLUSH);
  404. }
  405.  
  406.  
  407.  
  408. int
  409. lzwdecode (struct usock *up)
  410. {
  411. int32 code, data;
  412.  
  413.     if (up->zin->version == -1 && (up->zin->version = PULLCHAR (&up->ibuf))    == -1)
  414.         return -1;
  415.     if (up->zin->maxbits == -1) {
  416.         /* receive a recommended value for the maximum no of bits */
  417.         if ((up->zin->maxbits = PULLCHAR (&up->ibuf)) == -1)
  418.             return -1;
  419.         if (up->zout->maxbits > up->zin->maxbits) {
  420.             if (up->zout->codebits > up->zin->maxbits) {
  421.                 /* We are already using more bits than our
  422.                  * peer want us to, so clear the encoding
  423.                  * table immediately.
  424.                  */
  425.                 addtobuffer (up, up->zout->prefix);
  426.                 if (up->zout->next + 1 == (int32) 1 << up->zout->codebits)
  427.                     morebits (up->zout);
  428.                 addtobuffer (up, ZCC);
  429.                 cleartbl (up->zout);
  430.             }
  431.             up->zout->maxbits = up->zin->maxbits;
  432.         }
  433.     }
  434.     for (;;) {
  435.         if ((data = PULLCHAR (&up->zin->buf)) != -1)
  436.             return (int) data;
  437.         if ((code = nextcode (up)) == -1)
  438.             return -1;
  439.         decodetbl (code, up->zin);
  440.         up->zin->cnt += len_p (up->zin->buf);
  441.     }
  442. }
  443.  
  444.  
  445.  
  446. static void
  447. addchar (char data, struct lzw *lzw)
  448. {
  449.     lzw->buf = pushdown (lzw->buf, 1);
  450.     *lzw->buf->data = uchar(data);
  451. }
  452.  
  453.  
  454.  
  455. static void
  456. getstring (int32 code, struct lzw *lzw)
  457. {
  458. int i, j;
  459.  
  460.     for (;;) {
  461.         if (code < ZFLUSH) {
  462.             addchar ((char) code, lzw);
  463.             return;
  464.         }
  465.         i = (code - ZFLUSH - 1) / LZWBLK;
  466.         j = (code - ZFLUSH - 1) % LZWBLK;
  467.         addchar (lzw->tu.tbl[i][j].data, lzw);
  468.         code = (int32) lzw->tu.tbl[i][j].code;
  469.     }
  470. }
  471.  
  472.  
  473. static char
  474. firstchar (int32 code, struct lzw *lzw)
  475. {
  476. int i, j;
  477.  
  478.     for (;;) {
  479.         if (code < ZFLUSH)
  480.             return (char) code;
  481.         i = (code - ZFLUSH - 1) / LZWBLK;
  482.         j = (code - ZFLUSH - 1) % LZWBLK;
  483.         code = (int32) lzw->tu.tbl[i][j].code;
  484.     }
  485. }
  486.  
  487.  
  488. static void
  489. decodetbl (int32 code, struct lzw *lzw)
  490. {
  491. register unsigned int i, j;
  492. int32 pagelim;
  493.  
  494.     if (code > lzw->next) {
  495.         tcmdprintf ("LZW protocol error, process '%s'\n", Curproc->name);
  496.         return;
  497.     }
  498.     if (lzw->buf == NULLBUF) {
  499.         lzw->buf = ambufw (512);
  500.         /* allow us to use pushdown() later */
  501.         lzw->buf->data += lzw->buf->size;
  502.     }
  503.     if (lzw->prefix == -1) {
  504.         getstring (code, lzw);
  505.         lzw->prefix = code;
  506.         return;
  507.     }
  508.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  509.     if (lzw->tu.tbl == (struct zentry **) 0)
  510.         lzw->tu.tbl = (struct zentry **) callocw (1, sizeof (struct zentry *) * (unsigned long) pagelim);
  511.  
  512.     if (code < ZFLUSH)
  513.         goto intable;
  514.     i = (int16) ((code - ZFLUSH - 1) / LZWBLK);
  515.     j = (int16) (int) ((code - ZFLUSH - 1) % LZWBLK);
  516.     if (lzw->tu.tbl[i] == (struct zentry *) 0) {
  517.         lzw->tu.tbl[i] = (struct zentry *) mallocw (LZWBLK * sizeof (struct zentry));
  518.         memset ((char *) lzw->tu.tbl[i], 0xff, LZWBLK * sizeof (struct zentry));
  519.     }
  520.     if (lzw->tu.tbl[i][j].code == 0xffff) {
  521.         lzw->tu.tbl[i][j].data = firstchar (lzw->prefix, lzw);
  522.         lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  523.         getstring (code, lzw);
  524.         lzw->next = code + 1;
  525.         lzw->prefix = code;
  526.         if (lzw->next + 1 == (int32) 1 << lzw->codebits)
  527.             morebits (lzw);
  528.         return;
  529.     }
  530. intable:
  531.     getstring (code, lzw);
  532.     i = (int16) ((lzw->next - ZFLUSH - 1) / LZWBLK);
  533.     j = (int16) (int) ((lzw->next - ZFLUSH - 1) % LZWBLK);
  534.     if (lzw->tu.tbl[i] == (struct zentry *) 0) {
  535.         lzw->tu.tbl[i] = (struct zentry *) mallocw (LZWBLK * sizeof (struct zentry));
  536.         memset ((char *) lzw->tu.tbl[i], 0xff, LZWBLK * sizeof (struct zentry));
  537.     }
  538.     lzw->tu.tbl[i][j].data = firstchar (code, lzw);
  539.     lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  540.     lzw->next++;
  541.     lzw->prefix = code;
  542.     if (lzw->next + 1 == (int32) 1 << lzw->codebits)
  543.         morebits (lzw);
  544. }
  545.  
  546.  
  547.  
  548. /* extract the next codeword from the input stream */
  549. static int32
  550. nextcode (struct usock *up)
  551. {
  552. int32 code;
  553.  
  554.     if (up->zin->code == -1) {    /* read the first character */
  555.         if ((code = PULLCHAR (&up->ibuf)) == -1)
  556.             return -1;
  557.         up->zin->code = code >> up->zin->nextbit;    /*lint !e704 */
  558.     }
  559.     if (up->ibuf == NULLBUF)/* next byte is not available yet */
  560.         return -1;
  561.     /* continue assembling the codeword */
  562.     up->zin->code |= ((int32) uchar (*up->ibuf->data) << (8 - up->zin->nextbit)) & (((int32) 1 << up->zin->codebits) - 1);
  563.     if (16 - up->zin->nextbit < up->zin->codebits) {
  564.         (void) PULLCHAR (&up->ibuf);
  565.         up->zin->nextbit -= 8;    /* pull bits from a third byte */
  566.         return nextcode (up);
  567.     }
  568.     code = up->zin->code;
  569.     up->zin->code = -1;
  570.     up->zin->nextbit = (up->zin->nextbit + up->zin->codebits) % 8;
  571.     if (up->zin->nextbit == 0)
  572.         (void) PULLCHAR (&up->ibuf);
  573.     if (code == ZCC) {
  574.         cleartbl (up->zin);
  575.         return nextcode (up);
  576.     }
  577.     if (code == ZFLUSH) {
  578.         up->zin->prefix = -1;
  579.         return nextcode (up);
  580.     }
  581.     return code;
  582. }
  583.  
  584. #endif
  585.